package jzoffer;

import leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 之字层次遍历
 * @author MaoLin Wang
 * @date 2020/10/10 9:55 上午
 */
public class _32层次遍历3 {
    /**
     * 双栈
     * oddStack 放 奇数层节点 evenStack放偶数层节点
     * 偶数层的数据要左孩子先入evenStack栈，奇数层数据右孩子先入oddStack栈
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        Stack<TreeNode> evenStack = new Stack<>();
        Stack<TreeNode>oddStack=new Stack<>();
        int level=1;
        oddStack.push(root);
        /*
          level=1  oddStack.pop evenStack.push(left) evenStack.push(right)
          level=2 evenStack.pop oddStack.push(right) oddStack.push(left)
          level=3 oddStack.pop evenStack.push(left) evenStack.push(right)
         */
        List<List<Integer>>resList=new ArrayList<>();
        List<Integer>temp=null;
        while (!oddStack.isEmpty() || !evenStack.isEmpty()){
            temp=new ArrayList<>();

            if ((level & 1 )== 1){ //奇数层
                while (!oddStack.isEmpty()){
                    TreeNode node = oddStack.pop();
                    temp.add(node.val);
                    if (node.left!=null){
                        evenStack.push(node.left);
                    }
                    if (node.right!=null){
                        evenStack.push(node.right);
                    }
                }
                if (temp.size()>0){
                    resList.add(temp);
                }
            }else { //偶数层
                while (!evenStack.isEmpty()){
                    TreeNode node = evenStack.pop();
                    temp.add(node.val);
                    if (node.right!=null){
                        oddStack.push(node.right);
                    }
                    if (node.left!=null){
                        oddStack.push(node.left);
                    }
                }
                if (temp.size()>0){
                    resList.add(temp);
                }
            }
            level++;
        }
        return resList;
    }
}
